package com.arron.algorithm.leetcodetop100.双指针.n数之和;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


/**
 * 18. 四数之和
 */
public class 四数之和 {


    //[-2,-1,-1,1,1,2,2]
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length<4){
            return res;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            //去重
            if (i>0 &&  nums[i] == nums[i-1]){
                continue;
            }
            for (int j = i+1; j < nums.length; j++) {
                int l = j+1;
                int r = nums.length-1;
                //去重
                if (j>i+1 && nums[j] == nums[j-1]){
                    continue;
                }
                while (l<r){

                    long sum = (long) nums[i] + nums[j] + nums[l] + nums[r];
                    if (sum == target) {

                        res.add(Arrays.asList( nums[i] ,nums[j] , nums[l] , nums[r]));
                        //去重
                        while (l<r && nums[l]==nums[l+1]) l++;
                        while (l<r && nums[r]==nums[r-1]) r--;
                        if (l<r) l++; r--;
                    }else if ( sum< target){
                        l++;
                    }else {
                        r--;
                    }

                }


            }



        }
        return res;
    }


}
